﻿#pragma once
#include <ostream>

#include "FormatedUtil.h"
#include "Index.h"

class IMinestCostClimbStairs
{
public:
	/**
	* 最小花费爬楼梯.
	* https://www.nowcoder.com/practice/9b969a3ec20149e3b870b256ad40844e?tpId=230&tqId=2366449&ru=/exam/oj&qru=/ta/dynamic-programming/question-ranking&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D230
	*
	* 给定一个整数数组cost，其中cost[i]是从楼梯第i个台阶向上爬需要支付的费用，下标从0开始。一旦你支付此费用，即可选择向上爬一个或者两个台阶。
	* 你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
	* 请你计算并返回达到楼梯顶部的最低花费。
	*
	* 输入：
	* 3
	* 2 5 20
	* 输出：
    * 5
    * 说明：
	*	你将从下标为1的台阶开始，支付5 ，向上爬两个台阶，到达楼梯顶部。总花费为5 
	*/
	virtual int minestCostClimbStairs(std::vector<int>& cost) = 0;
};

class MinestCostClimbStairs
{
public:
	class DP:public IMinestCostClimbStairs
	{
	public:
		/**
		 * 动态规划:
		 * dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])
		 */
		int minestCostClimbStairs(std::vector<int>& cost) override
		{
			if (cost.empty())
				return 0;
			const int stairSize = cost.size();
			if (stairSize == 1)
				return cost[0];
			if (stairSize == 2)
				return std::min<int>(cost[0], cost[1]);

			int result = 0;
			//爬到前 i-1层和i-2层已花费的代价
			int dp[2] = { 0,0 };
			for (int i = 2; i <= stairSize; ++i)
			{
				result = std::min<>(dp[0] + cost[i - 2], dp[1] + cost[i - 1]);
				dp[0] = dp[1];
				dp[1] = result;
			}
			return result;
		}
	};
};

